#include <iostream>
#include <vector>
using namespace std;
/**
 * 1 <= nums.length <= 5000
 * -5000 <= nums[i] <= 5000
 * All the integers of nums are unique.
 * nums is sorted and rotated at some pivot.
 */
class Solution
{
public:
    /**
     * 不适用二分法，O(n)
     */
    int findMin_0(vector<int> &nums)
    {
        int numsLen = nums.size();
        int minV = nums[0];
        if (1 == numsLen)
        {
            return minV;
        }
        for (size_t i = 0; i < numsLen; i++)
        {
            if (minV > nums[i])
            {
                minV = nums[i];
            }
        }
        return minV;
    }

    /**
     * Binary search way
     * Time: O(logN)
     * Space: O(1)
     */
    int findMin_1(vector<int> &nums)
    {
        int numsLen = nums.size();
        if (numsLen == 1)
        {
            return nums[0];
        }
        int left = 0, right = numsLen - 1;

        // if the last element is greater than the first element then there is no rotation.
        // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
        // Hence the smallest element is first element. A[0]
        if (nums[right] > nums[0])
        {
            return nums[0];
        }

        // Binary search way
        while (right >= left)
        {
            // Find the mid element
            int mid = left + (right - left) / 2;

            // if the mid element is greater than its next element then mid+1 element is the smallest
            // This point would be the point of change. From higher to lower value.
            if (nums[mid] > nums[mid + 1])
            {
                return nums[mid + 1];
            }

            // if the mid element is lesser than its previous element then mid element is the smallest
            if (nums[mid - 1] > nums[mid])
            {
                return nums[mid];
            }

            // if the mid elements value is greater than the 0th element this means
            // the least value is still somewhere to the right as we are still dealing with elements
            // greater than nums[0]
            if (nums[mid] > nums[0])
            {
                left = mid + 1;
            }
            else
            {
                // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
                // the left
                right = mid - 1;
            }
        }
        return -1;
    }
    int findMin_2(vector<int> &nums)
    {
        int numsLen = nums.size();
        for (int i = 1; i < numsLen; ++i)
        {
            if (nums[i] < nums[i - 1])
            {
                return nums[i];
            }
        }
        return nums[0];
    }
};
int main()
{
    Solution solution;
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    cout << solution.findMin_1(nums) << endl;
    // system("pause");
    return 0;
}
